public class Solution704 {
    public int search(int[] nums, int target) {
        int l=0,r=nums.length-1,mid=(l+r)/2;
        while (l<=r){
            if (nums[mid]==target) return mid;
            if (nums[mid]>target) r=mid-1; else l=mid+1;
            mid=(l+r)/2;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution704().search(new int[]{-1,0,3,5,9,12},9));
    }
}
